Feature #11: Generate Movie Viewing Orders

Description#

We want to offer marathons for our viewers. Each marathon will have a fixed set of movies catering to a specific taste. For a given marathon, different viewing orders of the movies will yield different user satisfaction results. We want to experiment (A/B testing) with different viewing orders of the same marathon.

Your task is to generate all the possible permutations of movies in a given marathon.

Let’s look at an example to better understand this:

Solution#

To solve this problem, we will use the backtracking approach.

We will assume a backtrack function that takes the index of the first movie to consider as an argument backtrack(first).

• If the first movie to consider has index n, then that means that the current permutation is done.

• We will iterate over the marathon from index first to index n - 1.

• We will place the ith movie first in the permutation, that is, movies[first], movies[i] = movies[i], movies[first].

• We will proceed to create all the permutations that start from the ith movie: backtrack(first + 1).

• Now we will backtrack, that is, movies[first], movies[i] = movies[i], movies[first] back.

Let’s look at some illustrations to better understand this:

Note: We are using numbers to represent movies in the following illustration.

Let’s look at the code for this solution:

Complexity measures#

Time complexity#

The algorithm takes ${O}(n!)$ time complexity, wherein $n$ is the movies size and ${\displaystyle n!=n\cdot (n-1)\cdot (n-2)\cdot (n-3)\cdot \cdots \cdot 3\cdot 2\cdot 1\,.}$

Space complexity#

The algorithm will take ${O}(n)$ space complexity because the maximum stack depth is $n$, the height of any branch from the root to any leaf.